#include "common.h"

int search(int* nums, int numsSize, int target);

int main()
{
	return 0;
}

int search(int* nums, int numsSize, int target)
{
	int lo = 0, hi = numsSize, beacon = target >= nums[0];
	while (lo < hi) {
		int mid = lo + (hi - lo >> 1);
		if (nums[mid] == target)
			return mid;

		if (beacon) {
			if (nums[mid] < nums[0])
				nums[mid] = 0x7FFFffff;
		} else if (nums[mid] >= nums[0])
			nums[mid] = 0x80000000;

		if (nums[mid] < target)
			lo = mid + 1;
		else
			hi = mid;
	}
	return -1;
}
